#include "myGraph.h"
#include <iostream>
#include <sstream>
#include <string>
#include <queue>

using namespace std;

EdgeNode::EdgeNode(){
    link=NULL;
}

EdgeNode::EdgeNode(int d, EdgeNode* l){
    dest=d;
    link=l;
}

EdgeNode::~EdgeNode(){
}

int EdgeNode::getDest(){
    return dest;
}

EdgeNode* EdgeNode::getNext(){
    return link;
}

void EdgeNode::setDest(int d){
    dest=d;
}

void EdgeNode::setNext(EdgeNode* l){
    link=l;
}

VertexNode::VertexNode(){
    firstEdge=NULL;
}

VertexNode::VertexNode(char d, EdgeNode* first){
    data=d;
    firstEdge=first;
}

VertexNode::~VertexNode(){

}

char VertexNode::getData(){
    return data;
}

EdgeNode* VertexNode::getFirstEdge(){
    return firstEdge;
}

void VertexNode::setData(char d){
    data=d;
}

void VertexNode::setFirstEdge(EdgeNode* first){
    firstEdge=first;
}

MyGraph::MyGraph(){
    nodeNum=0;
    edgeNum=0;
    VexList=NULL;
}

MyGraph::MyGraph(int nodeNum, int edgeNum, char* nodeList, int* edgeStartList, int* edgeEndList){
    this->nodeNum=nodeNum;
    this->edgeNum=edgeNum;
    VexList=new VertexNode[nodeNum]; 
    for(int i=0;i<nodeNum;i++)
    {
        VexList[i].setData(nodeList[i]);
    }
    for(int i=0;i<edgeNum;i++)
    {
        EdgeNode* temp1=new EdgeNode(edgeEndList[i],VexList[edgeStartList[i]].firstEdge);
        VexList[edgeStartList[i]].firstEdge=temp1;
        EdgeNode* temp2=new EdgeNode(edgeStartList[i],VexList[edgeEndList[i]].firstEdge);
        VexList[edgeEndList[i]].firstEdge=temp2;
    }
}

MyGraph::~MyGraph(){
    for(int i=0;i<nodeNum;i++)
    {
        while(VexList[i].firstEdge!=NULL)
        {
            EdgeNode* temp;
            temp=VexList[i].firstEdge;
            VexList[i].firstEdge=VexList[i].firstEdge->link;
            delete temp;
        }
    }
    delete [] VexList;
}

int MyGraph::getNodeNum(){
    return nodeNum;
}

int MyGraph::getEdgeNum(){
    return edgeNum;
}

string MyGraph::printGraph(){
    string str="";
    for(int i=0;i<nodeNum;i++)
    {
        str=str+VexList[i].data;
        str=str+":";
        EdgeNode* curNode=VexList[i].firstEdge;
        while(curNode!=NULL)
        {
            str=str+" ";
            str=str+VexList[curNode->dest].data;
            curNode=curNode->link;
        }
        if(i!=nodeNum-1)
        {
            str=str+"\n";
        }
    }
    return str;
}
void MyGraph::DFS(int v, int* visited, string& result){
    result=result+VexList[v].data;
    result=result+" ";
    visited[v]=1;
    EdgeNode* curNode=VexList[v].firstEdge;
    while(curNode!=NULL)
    {
        if(!visited[curNode->dest])
        {
            DFS(curNode->dest,visited,result);
            
        }
        curNode=curNode->link;
    }
    return;
}

string MyGraph::graph_DFS_Traverse(){
    string result="";
    int *visited=new int[nodeNum];
    for(int i=0;i<nodeNum;i++)
    {
        visited[i]=0;
    }
    for(int i=0;i<nodeNum;i++)
    {
        if(!visited[i])
        {
            DFS(i,visited,result);
        }
    }
    delete [] visited;
    return result;
}

void MyGraph::BFS(int v, int* visited, string& result){
    queue<int> search;
    search.push(v);
    visited[search.front()]=1;
    while(!search.empty())
    {
        result=result+VexList[search.front()].data;
        result=result+" ";
        EdgeNode* curNode=VexList[search.front()].firstEdge;
        while(curNode!=NULL)
        {
            if(!visited[curNode->dest])
            {
                search.push(curNode->dest);
                visited[curNode->dest]=1;
            }
            curNode=curNode->link;
        }
        search.pop();
    }
}

string MyGraph::graph_BFS_Traverse(){
    string result="";
    int *visited=new int[nodeNum];
    for(int i=0;i<nodeNum;i++)
    {
        visited[i]=0;
    }
    for(int i=0;i<nodeNum;i++)
    {
        if(!visited[i])
        {
            BFS(i,visited,result);
        }
    }
    delete [] visited;
    return result;
}